{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #English Int LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #math #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #数学 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberToWords"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #整数的英语表示"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数，打印该整数的英文描述。</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> 123\n",
    "<strong>输出:</strong> \"One Hundred Twenty Three\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> 12345\n",
    "<strong>输出:</strong> \"Twelve Thousand Three Hundred Forty Five\"</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> 1234567\n",
    "<strong>输出:</strong> \"One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven\"</pre>\n",
    "\n",
    "<p><strong>示例 4:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> 1234567891\n",
    "<strong>输出:</strong> \"One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One\"</pre>\n",
    "\n",
    "<p>注意：本题与 273 题相同：<a href=\"https://leetcode-cn.com/problems/integer-to-english-words/\">https://leetcode-cn.com/problems/integer-to-english-words/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [english-int-lcci](https://leetcode.cn/problems/english-int-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [english-int-lcci](https://leetcode.cn/problems/english-int-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "\n",
    "        def trans_ones(num):\n",
    "            return ('', 'One', 'Two', 'Three', 'Four', 'Five',\n",
    "                    'Six', 'Seven', 'Eight', 'Nine', 'Ten',\n",
    "                    'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen',\n",
    "                    'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen')[num]\n",
    "\n",
    "        def trans_tens(num):\n",
    "            return (None, None, 'Twenty', 'Thirty', 'Forty',\n",
    "                    'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety')[num // 10]\n",
    "\n",
    "        def parse_digits(num):\n",
    "            res = []\n",
    "            if num // 100 > 0:\n",
    "                res.append(trans_ones(num // 100) + ' Hundred')\n",
    "            num %= 100\n",
    "            if num < 20:\n",
    "                res.append(trans_ones(num))\n",
    "            else:\n",
    "                res.append(trans_tens(num))\n",
    "                res.append(trans_ones(num % 10))\n",
    "            return ' '.join(res).strip()\n",
    "        \n",
    "        ans = ''\n",
    "        for subfix in ('', 'Thousand', 'Million', 'Billion'):\n",
    "            if num > 0:\n",
    "                part = parse_digits(num % 1000)\n",
    "                if part:\n",
    "                    ans = ' '.join([part, subfix, ans])\n",
    "            num //= 1000\n",
    "        return ans.strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num==0:\n",
    "            return 'Zero'\n",
    "        def recursion(num):\n",
    "            s=''\n",
    "            if num==0:\n",
    "                return s\n",
    "            elif num<10:\n",
    "                s+=singles[num]+\" \"\n",
    "            elif num<20:\n",
    "                s+=teens[num-10]+\" \"\n",
    "            elif num<100:\n",
    "                s+=tens[num//10]+\" \"+recursion(num%10)\n",
    "            else:\n",
    "                s+=singles[num//100]+\" Hundred \"+recursion(num%100)\n",
    "            return s\n",
    "        s=\"\"\n",
    "        unit=int(1e9)\n",
    "        for i in range(3,-1,-1):\n",
    "            curNum=num//unit\n",
    "            if curNum:\n",
    "                num-=curNum*unit\n",
    "                s+=recursion(curNum)+thousands[i]+\" \"\n",
    "            unit//=1000\n",
    "        return s.strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        one = ['Zero','One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine']\n",
    "        teen = ['Ten','Eleven','Twelve','Thirteen','Fourteen','Fifteen','Sixteen','Seventeen','Eighteen','Nineteen']\n",
    "        ty = ['', '', 'Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety']\n",
    "        def less1000(x):\n",
    "            res = []\n",
    "            if x >= 100:\n",
    "                res.append(one[x // 100] + ' Hundred')\n",
    "                x %= 100\n",
    "            if x >= 20:\n",
    "                res.append(ty[x // 10])\n",
    "                x %= 10\n",
    "            elif x >= 10:\n",
    "                res.append(teen[x - 10])\n",
    "                x %= 10\n",
    "                return ' '.join(res)\n",
    "            if x > 0:\n",
    "                res.append(one[x])\n",
    "            return ' '.join(res)\n",
    "        ans = []\n",
    "        if num == 0:\n",
    "            return 'Zero'\n",
    "        if num >= 1000 * 1000 * 1000:\n",
    "            ans.append(one[num // (1000 * 1000 * 1000)] + ' Billion')\n",
    "            num %= (1000 * 1000 * 1000)\n",
    "        if num >= 1000 * 1000:\n",
    "            ans.append(less1000(num // (1000 * 1000)) + ' Million')\n",
    "            num %= (1000 * 1000)\n",
    "        if num >= 1000:\n",
    "            ans.append(less1000(num // 1000) + ' Thousand')\n",
    "            num %= 1000\n",
    "        if num > 0:\n",
    "            ans.append(less1000(num))\n",
    "        return ' '.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        val = {1:'One',2:'Two',3:'Three',4:'Four',5:'Five',6:'Six',7:'Seven',8:'Eight',9:'Nine',10:'Ten',11:'Eleven',12:'Twelve',13:'Thirteen',14:'Fourteen',15:'Fifteen',16:'Sixteen',17:'Seventeen',18:'Eighteen',19:'Nineteen',20:'Twenty',30:'Thirty',40:'Forty',50:'Fifty',60:'Sixty',70:'Seventy',80:'Eighty',90:'Ninety'}\n",
    "        acc = ['Thousand','Million','Billion','Trillion']\n",
    "        if num==0:return 'Zero'\n",
    "        def func(num):\n",
    "            re,i = '',1\n",
    "            if num>=100:\n",
    "                re = val[num//100]+' '+'Hundred'\n",
    "            num %= 100\n",
    "            if 0<num<=20:\n",
    "                re += ' '+val[num]\n",
    "            elif 20<=num<100:\n",
    "                re += ' '+val[num-num%10]+' '+val[num%10] if num%10 else ' '+val[num]\n",
    "            return re.strip(' ')\n",
    "\n",
    "        k = -1\n",
    "        res = ''\n",
    "        while num>0:\n",
    "            tmp = num%1000\n",
    "            if tmp:\n",
    "                ans = func(tmp)+' '+acc[k] if k>-1 else func(tmp)\n",
    "                res = ans+' '+res\n",
    "            num //= 1000\n",
    "            k+=1\n",
    "        return res.strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "nums = {\n",
    "    0: \"\",\n",
    "    1: \"One\",\n",
    "    2: \"Two\",\n",
    "    3: \"Three\",\n",
    "    4: \"Four\",\n",
    "    5: \"Five\",\n",
    "    6: \"Six\",\n",
    "    7: \"Seven\",\n",
    "    8: \"Eight\",\n",
    "    9: \"Nine\",\n",
    "    10: \"Ten\",\n",
    "    11: \"Eleven\",\n",
    "    12: \"Twelve\",\n",
    "    13: \"Thirteen\",\n",
    "    14: \"Fourteen\",\n",
    "    15: \"Fifteen\",\n",
    "    16: \"Sixteen\",\n",
    "    17: \"Seventeen\",\n",
    "    18: \"Eighteen\",\n",
    "    19: \"Nineteen\",\n",
    "    20: \"Twenty\",\n",
    "    30: \"Thirty\",\n",
    "    40: \"Forty\",\n",
    "    50: \"Fifty\",\n",
    "    60: \"Sixty\",\n",
    "    70: \"Seventy\",\n",
    "    80: \"Eighty\",\n",
    "    90: \"Ninety\",\n",
    "    100: \"Hundred\",\n",
    "    1_000: \"Thousand\",\n",
    "    1_000_000: \"Million\",\n",
    "    1_000_000_000: \"Billion\",\n",
    "}\n",
    "\n",
    "\n",
    "\n",
    "def f(x: int) -> str:\n",
    "\n",
    "    if x >= 1_000_000_000:\n",
    "        return f\"{f(x // 1_000_000_000)} {nums[1_000_000_000]} {f(x % 1_000_000_000)}\"\n",
    "\n",
    "    elif x >= 1_000_000:\n",
    "        return f\"{f(x // 1_000_000)} {nums[1_000_000]} {f(x % 1_000_000)}\"\n",
    "\n",
    "    elif x >= 1_000:\n",
    "        return f\"{f(x // 1_000)} {nums[1_000]} {f(x % 1_000)}\"\n",
    "    \n",
    "    elif x >= 100:\n",
    "        return f\"{f(x // 100)} {nums[100]} {f(x % 100)}\"\n",
    "\n",
    "    elif x > 20:\n",
    "        return f\"{nums[x // 10 * 10]} {nums[x % 10]}\"\n",
    "    \n",
    "    else:\n",
    "        return nums[x]\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        return \" \".join(f(num).split()) if num > 0 else \"Zero\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        val = {1:'One',2:'Two',3:'Three',4:'Four',5:'Five',6:'Six',7:'Seven',8:'Eight',9:'Nine',10:'Ten',11:'Eleven',12:'Twelve',13:'Thirteen',14:'Fourteen',15:'Fifteen',16:'Sixteen',17:'Seventeen',18:'Eighteen',19:'Nineteen',20:'Twenty',30:'Thirty',40:'Forty',50:'Fifty',60:'Sixty',70:'Seventy',80:'Eighty',90:'Ninety'}\n",
    "        acc = ['Thousand','Million','Billion','Trillion']\n",
    "        if num==0:return 'Zero'\n",
    "        def func(num):\n",
    "            re,i = '',1\n",
    "            if num>=100:\n",
    "                re = val[num//100]+' '+'Hundred'\n",
    "            num %= 100\n",
    "            if 0<num<=20:\n",
    "                re += ' '+val[num]\n",
    "            elif 20<=num<100:\n",
    "                re += ' '+val[num-num%10]+' '+val[num%10] if num%10 else ' '+val[num]\n",
    "            return re.strip(' ')\n",
    "\n",
    "        k = -1\n",
    "        res = ''\n",
    "        while num>0:\n",
    "            tmp = num%1000\n",
    "            if tmp:\n",
    "                ans = func(tmp)+' '+acc[k] if k>-1 else func(tmp)\n",
    "                res = ans+' '+res\n",
    "            num //= 1000\n",
    "            k+=1\n",
    "        return res.strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "\n",
    "        l_1_9 = [\"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "        l_10_19 = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\",\n",
    "                   \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "        l_20_90 = [\"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "        n100 = \" Hundred\"\n",
    "        n1000 = \" Thousand\"\n",
    "        n100w = \" Million\"\n",
    "        n10y = \" Billion\"\n",
    "\n",
    "        def get_3(num):\n",
    "            h, num = divmod(num, 100)\n",
    "            if h:\n",
    "                if num == 0:\n",
    "                    return l_1_9[h - 1] + n100\n",
    "                ret = l_1_9[h - 1] + n100 + \" \"\n",
    "            else:\n",
    "                ret = \"\"\n",
    "\n",
    "            if num < 10:\n",
    "                return ret + l_1_9[num - 1]\n",
    "            if num < 20:\n",
    "                return ret + l_10_19[num - 10]\n",
    "\n",
    "            t, num = divmod(num, 10)\n",
    "            if num == 0:\n",
    "                return ret + l_20_90[t - 2]\n",
    "            return ret + l_20_90[t - 2] + \" \" + l_1_9[num - 1]\n",
    "\n",
    "        b, num = divmod(num, 1000000000)\n",
    "        if num == 0:\n",
    "            return get_3(b) + n10y\n",
    "        elif b:\n",
    "            ret = get_3(b) + n10y + \" \"\n",
    "        else:\n",
    "            ret = \"\"\n",
    "\n",
    "        m, num = divmod(num, 1000000)\n",
    "        if num == 0:\n",
    "            return ret + get_3(m) + n100w\n",
    "        elif m:\n",
    "            ret += get_3(m) + n100w + \" \"\n",
    "\n",
    "        t, num = divmod(num, 1000)\n",
    "        if num == 0:\n",
    "            return ret + get_3(t) + n1000\n",
    "        elif t:\n",
    "            return ret + get_3(t) + n1000 + \" \" + get_3(num)\n",
    "        return ret + get_3(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        self.digits = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "        self.teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "        self.tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "        self.thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "\n",
    "        if num == 0: return \"Zero\"\n",
    "        ans = \"\"\n",
    "        unit = 1000000000\n",
    "        for i in range(3, -1, -1):\n",
    "            curNum = num // unit\n",
    "            if curNum > 0:\n",
    "                num -= (curNum * unit)\n",
    "                ans += self.recur(curNum)\n",
    "                ans += (self.thousands[i] + \" \")\n",
    "            unit /= 1000\n",
    "        \n",
    "        return ans.strip()\n",
    "\n",
    "\n",
    "    def recur(self, num):\n",
    "        num = int(num)\n",
    "        if num == 0: return \"\"\n",
    "        if num < 10: return self.digits[num] + \" \"\n",
    "        if num < 20: return self.teens[num-10] + \" \"\n",
    "        if num < 100:\n",
    "            return self.tens[num // 10] + \" \" + self.recur(num % 10)\n",
    "        return self.digits[num // 100] + \" Hundred \" + self.recur(num % 100)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "        \n",
    "        def one(num):\n",
    "            switcher = {\n",
    "                1: 'One',\n",
    "                2: 'Two',\n",
    "                3: 'Three',\n",
    "                4: 'Four',\n",
    "                5: 'Five',\n",
    "                6: 'Six',\n",
    "                7: 'Seven',\n",
    "                8: 'Eight',\n",
    "                9: 'Nine'\n",
    "            }\n",
    "            return switcher.get(num)\n",
    "        \n",
    "        def two_less_20(num):\n",
    "            switcher = {\n",
    "                10: 'Ten',\n",
    "                11: 'Eleven',\n",
    "                12: 'Twelve',\n",
    "                13: 'Thirteen',\n",
    "                14: 'Fourteen',\n",
    "                15: 'Fifteen',\n",
    "                16: 'Sixteen',\n",
    "                17: 'Seventeen',\n",
    "                18: 'Eighteen',\n",
    "                19: 'Nineteen'\n",
    "            }\n",
    "            return switcher.get(num)\n",
    "        \n",
    "        def ten(num):\n",
    "            switcher = {\n",
    "                2: 'Twenty',\n",
    "                3: 'Thirty',\n",
    "                4: 'Forty',\n",
    "                5: 'Fifty',\n",
    "                6: 'Sixty',\n",
    "                7: 'Seventy',\n",
    "                8: 'Eighty',\n",
    "                9: 'Ninety'\n",
    "            }\n",
    "            return switcher.get(num)\n",
    "        \n",
    "        def two(num):\n",
    "            if not num:\n",
    "                return ''\n",
    "            elif num < 10:\n",
    "                return one(num)\n",
    "            elif num < 20:\n",
    "                return two_less_20(num)\n",
    "            else:\n",
    "                tenner = num // 10\n",
    "                rest = num - tenner * 10\n",
    "                return ten(tenner) + ' ' + one(rest) if rest else ten(tenner)\n",
    "        \n",
    "        def three(num):\n",
    "            hundred = num // 100\n",
    "            rest = num - hundred * 100\n",
    "            if hundred and rest:\n",
    "                return one(hundred) + ' Hundred ' + two(rest)\n",
    "            elif not hundred and rest:\n",
    "                return two(rest)\n",
    "            elif hundred and not rest:\n",
    "                return one(hundred) + ' Hundred'\n",
    "        \n",
    "        billion = num // 1000000000\n",
    "        million = (num - billion * 1000000000) // 1000000\n",
    "        thousand = (num - billion * 1000000000 - million * 1000000) // 1000\n",
    "        remainder = num - billion * 1000000000 - million * 1000000 - thousand * 1000\n",
    "        \n",
    "        result = ''\n",
    "        if billion:        \n",
    "            result = three(billion) + ' Billion'\n",
    "        if million:\n",
    "            result += ' ' if result else ''    \n",
    "            result += three(million) + ' Million'\n",
    "        if thousand:\n",
    "            result += ' ' if result else ''\n",
    "            result += three(thousand) + ' Thousand'\n",
    "        if remainder:\n",
    "            result += ' ' if result else ''\n",
    "            result += three(remainder)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num==0:\n",
    "            return 'Zero'\n",
    "        singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "        teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\",\"Nineteen\"]\n",
    "        tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "        thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "\n",
    "        def recursion(num):\n",
    "            cur=''\n",
    "            if num==0:\n",
    "                return cur\n",
    "\n",
    "            if num>=100:\n",
    "                cur+=' '+(singles[num//100])+' '+'Hundred'+recursion(num%100)\n",
    "                return cur\n",
    "            if num>=20:\n",
    "                cur+=' '+(tens[num//10])+ recursion(num%10)\n",
    "                return  cur\n",
    "\n",
    "            if 10<=num<20:\n",
    "                cur+=' '+(teens[int(num%10)])\n",
    "                return cur\n",
    "            elif num<10:\n",
    "                cur+=' '+singles[num]\n",
    "                return cur\n",
    "\n",
    "        number=10**9\n",
    "        result=''\n",
    "        index=3\n",
    "        while number!=1:\n",
    "            if num//number==0:\n",
    "                num=num%number\n",
    "                number//=1000\n",
    "                index-=1\n",
    "                continue\n",
    "            else:\n",
    "                result+=recursion(num//number)+' '+thousands[index]\n",
    "            num=num%number\n",
    "            number//=1000\n",
    "            index-=1\n",
    "        result+=recursion(num)\n",
    "\n",
    "        return result.strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num==0:\n",
    "            return 'Zero'\n",
    "        def recursion(num):\n",
    "            s=''\n",
    "            if num==0:\n",
    "                return s\n",
    "            elif num<10:\n",
    "                s+=singles[num]+\" \"\n",
    "            elif num<20:\n",
    "                s+=teens[num-10]+\" \"\n",
    "            elif num<100:\n",
    "                s+=tens[num//10]+\" \"+recursion(num%10)\n",
    "            else:\n",
    "                s+=singles[num//100]+\" Hundred \"+recursion(num%100)\n",
    "            return s\n",
    "        s=\"\"\n",
    "        unit=int(1e9)\n",
    "        for i in range(3,-1,-1):\n",
    "            curNum=num//unit\n",
    "            if curNum:\n",
    "                num-=curNum*unit\n",
    "                s+=recursion(curNum)+thousands[i]+\" \"\n",
    "            unit//=1000\n",
    "        return s.strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        s = str(num)\n",
    "        # n = len(s)\n",
    "        # nums = [\"\"] * 20\n",
    "        mmp = {'0':\"Zero\",'1':\"One\",'2':\"Two\",'3':\"Three\",'4':\"Four\",'5':\"Five\",'6':\"Six\",'7':\"Seven\",'8':\"Eight\",'9':\"Nine\",\"10\":\"Ten\",\n",
    "                \"11\":\"Eleven\",\"12\":\"Twelve\",\"13\":\"Thirteen\",\"14\":\"Fourteen\",\"15\":\"Fifteen\",\"16\":\"Sixteen\",\"17\":\"Seventeen\",\"18\":\"Eighteen\",\"19\":\"Nineteen\",\n",
    "                \"20\":\"Twenty\",\"30\":\"Thirty\",\"40\":\"Forty\",\"50\":\"Fifty\",\"60\":\"Sixty\",\"70\":\"Seventy\",\"80\":\"Eighty\",\"90\":\"Ninety\",\n",
    "                '100':\"One Hundred\",'200':\"Two Hundred\",'300':\"Three Hundred\",'400':\"Four Hundred\",'500':\"Five Hundred\",'600':\"Six Hundred\",\n",
    "                '700':\"Seven Hundred\",'800':\"Eight Hundred\",'900':\"Nine Hundred\"}\n",
    "        sp = [\"Thousand\",\"Million\",\"Billion\"]\n",
    "\n",
    "        ans = []\n",
    "        idx = 0\n",
    "        while True:\n",
    "            ss = \"\"\n",
    "            ns = s[-3:]\n",
    "            s = s[:-3]\n",
    "\n",
    "            if len(ns) == 3 and ns[-3] != \"0\":\n",
    "                ss += mmp[ns[-3] + \"00\"] + \" \"\n",
    "            if ns[-2:] != \"00\":\n",
    "                if len(ns) >= 2:\n",
    "                    if ns[-2:] in mmp:\n",
    "                        ss += mmp[ns[-2:]]\n",
    "                    elif ns[-2] != \"0\":\n",
    "                        ss += mmp[ns[-2] + '0'] + \" \" + mmp[ns[-1]]\n",
    "                    else:\n",
    "                        ss += mmp[ns[-1]]\n",
    "                else:\n",
    "                    ss += mmp[ns[-1]]\n",
    "            # print(ss)\n",
    "            ans.insert(0,ss)\n",
    "            if s:\n",
    "                ans.insert(0,sp[idx])\n",
    "                idx += 1\n",
    "            else:\n",
    "                break\n",
    "        # print(ans)\n",
    "        return \" \".join(ans).strip().replace(\"  \",\" \").replace(\"Million Thousand\", \"Million\").replace(\"Billion Million\", \"Billion\")\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "\n",
    "        def toEnglish(num: int) -> str:\n",
    "            s = \"\"\n",
    "            if num >= 100:\n",
    "                s += singles[num // 100] + \" Hundred \"\n",
    "                num %= 100\n",
    "            if num >= 20:\n",
    "                s += tens[num // 10] + \" \"\n",
    "                num %= 10\n",
    "            if 0 < num < 10:\n",
    "                s += singles[num] + \" \"\n",
    "            elif num >= 10:\n",
    "                s += teens[num - 10] + \" \"\n",
    "            return s\n",
    "\n",
    "        s = \"\"\n",
    "        unit = int(1e9)\n",
    "        for i in range(3, -1, -1):\n",
    "            curNum = num // unit\n",
    "            if curNum:\n",
    "                num -= curNum * unit\n",
    "                s += toEnglish(curNum) + thousands[i] + \" \"\n",
    "            unit //= 1000\n",
    "        return s.strip()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "        num_str_segs = []\n",
    "        suffix = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "        suffix_index = 0\n",
    "        unit_digit_str = [\n",
    "            \"\",\n",
    "            \"One\",\n",
    "            \"Two\",\n",
    "            \"Three\",\n",
    "            \"Four\",\n",
    "            \"Five\",\n",
    "            \"Six\",\n",
    "            \"Seven\",\n",
    "            \"Eight\",\n",
    "            \"Nine\",\n",
    "        ]\n",
    "        ten_digit_str = [\n",
    "            \"\",\n",
    "            \"\",\n",
    "            \"Twenty\",\n",
    "            \"Thirty\",\n",
    "            \"Forty\",\n",
    "            \"Fifty\",\n",
    "            \"Sixty\",\n",
    "            \"Seventy\",\n",
    "            \"Eighty\",\n",
    "            \"Ninety\",\n",
    "        ]\n",
    "        double_digit_str = [\n",
    "            \"Ten\",\n",
    "            \"Eleven\",\n",
    "            \"Twelve\",\n",
    "            \"Thirteen\",\n",
    "            \"Fourteen\",\n",
    "            \"Fifteen\",\n",
    "            \"Sixteen\",\n",
    "            \"Seventeen\",\n",
    "            \"Eighteen\",\n",
    "            \"Nineteen\",\n",
    "        ]\n",
    "        while num != 0:\n",
    "            seg_num = num % 1000\n",
    "            num //= 1000\n",
    "            segs = []\n",
    "            hundred_digit = seg_num // 100\n",
    "            segs = []\n",
    "            if hundred_digit > 0:\n",
    "                segs.append(unit_digit_str[hundred_digit] + \" Hundred\")\n",
    "            ten_digit = (seg_num // 10) % 10\n",
    "            if ten_digit == 1:\n",
    "                segs.append(double_digit_str[seg_num % 10])\n",
    "            else:\n",
    "                if ten_digit > 1:\n",
    "                    segs.append(ten_digit_str[ten_digit])\n",
    "                unit_digit = seg_num % 10\n",
    "                if unit_digit > 0:\n",
    "                    segs.append(unit_digit_str[unit_digit])\n",
    "            if seg_num > 0 and suffix_index > 0:\n",
    "                segs.append(suffix[suffix_index])\n",
    "            if len(segs) > 0:\n",
    "                num_str_segs.append(\" \".join(segs))\n",
    "            suffix_index += 1\n",
    "        num_str_segs.reverse()\n",
    "        return \" \".join(num_str_segs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0: return 'Zero'\n",
    "        res = []\n",
    "        decade = ['Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen',\n",
    "                  'Seventeen', 'Eighteen', 'Nineteen']\n",
    "        unit = ['One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine']\n",
    "        bigDecade = ['Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety']\n",
    "        magnitude = ['Billion', 'Million', 'Thousand']\n",
    "\n",
    "        def ThreeDigitStr(inStr1):\n",
    "            inStr1 = str(int(inStr1))\n",
    "            m = len(inStr1)\n",
    "            if int(inStr1) == 0: return None\n",
    "            if m == 1: return unit[int(inStr1)-1]\n",
    "            if 10 <= int(inStr1[-2:]) < 20:\n",
    "                deStr = decade[int(inStr1)%10]\n",
    "                if m == 3:\n",
    "                    return unit[int(inStr1[0])-1] + ' Hundred ' + deStr\n",
    "                else:\n",
    "                    return deStr\n",
    "            if m == 2:\n",
    "                if int(inStr1[1]) > 0:\n",
    "                    return bigDecade[int(inStr1[0])-2]+' '+unit[int(inStr1[1])-1]\n",
    "                else:\n",
    "                    return bigDecade[int(inStr1[0]) - 2]\n",
    "            elif m == 3:\n",
    "                twoUnit = ThreeDigitStr(inStr1[1:])\n",
    "                if twoUnit:\n",
    "                    return unit[int(inStr1[0])-1]+' Hundred '+twoUnit\n",
    "                else:\n",
    "                    return unit[int(inStr1[0]) - 1] + ' Hundred'\n",
    "\n",
    "        inStr = str(num)\n",
    "        n = len(inStr)\n",
    "        for idx in range(0, n, 3):\n",
    "            tempIdx = -idx-3 if -idx-3 >= -n else 0\n",
    "            if idx == 0:\n",
    "                tempStr = inStr[tempIdx:]\n",
    "            else:\n",
    "                tempStr = inStr[tempIdx:-idx]\n",
    "            ret = ThreeDigitStr(tempStr)\n",
    "            if ret:\n",
    "                if idx >= 3:\n",
    "                    if len(res) > 0:\n",
    "                        res.append(' ')\n",
    "                    res.append(' '+magnitude[-(idx//3)])\n",
    "                res.append(ret)\n",
    "        return ''.join(res[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0: return \"Zero\"\n",
    "\n",
    "        under_20 = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\", \"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "        tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "        \n",
    "        def toWords(n):\n",
    "            if n >= 1000000000:\n",
    "                return toWords(n // 1000000000) + \" Billion\" + toWords(n % 1000000000)\n",
    "            elif n >= 1000000:\n",
    "                return toWords(n // 1000000) + \" Million\" + toWords(n % 1000000)\n",
    "            elif n >= 1000:\n",
    "                return toWords(n // 1000) + \" Thousand\" + toWords(n % 1000)\n",
    "            elif n >= 100:\n",
    "                return toWords(n // 100) + \" Hundred\" + toWords(n % 100)\n",
    "            elif n >= 20:\n",
    "                return \" \" + tens[n // 10] + toWords(n % 10)\n",
    "            elif n >= 1:\n",
    "                return \" \" + under_20[n]\n",
    "            else:\n",
    "                return \"\"\n",
    "\n",
    "        return toWords(num).strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return 'Zero'\n",
    "        single_list = ['Zero', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine']\n",
    "        ten_to_nineteen_list = ['Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen']\n",
    "        Twenty_to_Ninety_list = ['Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', \"Ninety\"]\n",
    "        Three_segmented_list = ['Hundred', 'Thousand', 'Million', 'Billion']\n",
    "        num_str = str(num)\n",
    "        num_str_length = len(num_str)\n",
    "        answer_list = list()\n",
    "        dfs(answer_list, num_str, num_str_length, 0, num_str_length - 1, single_list, ten_to_nineteen_list, Twenty_to_Ninety_list, Three_segmented_list)\n",
    "        return ''.join(answer_list)\n",
    "\n",
    "def translate_3(num_str, Twenty_to_Ninety_list, ten_to_nineteen_list, single_list, answer_list):\n",
    "    if num_str[0] != '0':\n",
    "        answer_list.append(single_list[int(num_str[0])])\n",
    "        answer_list.append(' ')\n",
    "        answer_list.append('Hundred')\n",
    "        answer_list.append(' ')\n",
    "    if num_str[1] != '0':\n",
    "        if num_str[1] == '1':\n",
    "            answer_list.append(ten_to_nineteen_list[int(num_str[2])])\n",
    "            answer_list.append(' ')\n",
    "            return\n",
    "        else:\n",
    "            answer_list.append(Twenty_to_Ninety_list[int(num_str[1]) - 2])\n",
    "            answer_list.append(' ')\n",
    "    if num_str[2] != '0':\n",
    "        answer_list.append(single_list[int(num_str[2])])\n",
    "        answer_list.append(' ')\n",
    "\n",
    "def translate_21(num_str, Twenty_to_Ninety_list, ten_to_nineteen_list, single_list, answer_list):\n",
    "    if len(num_str) == 2:\n",
    "        if num_str[0] != '0':\n",
    "            if num_str[0] == '1':\n",
    "                answer_list.append(ten_to_nineteen_list[int(num_str[1])])\n",
    "                answer_list.append(' ')\n",
    "                return \n",
    "            else:\n",
    "                answer_list.append(Twenty_to_Ninety_list[int(num_str[0]) - 2])\n",
    "                answer_list.append(' ')\n",
    "                if num_str[1] != '0':\n",
    "                    answer_list.append(single_list[int(num_str[1])])\n",
    "                    answer_list.append(' ')\n",
    "    else:\n",
    "        if num_str[0] != '0':\n",
    "            answer_list.append(single_list[int(num_str[0])])\n",
    "            answer_list.append(' ')\n",
    "\n",
    "def dfs(answer_list, num_str, num_str_length, layer, start_index, single_list, ten_to_nineteen_list, Twenty_to_Ninety_list, Three_segmented_list):\n",
    "    if num_str_length - 3 >= 0:\n",
    "        num_str_length -= 3 \n",
    "        dfs(answer_list, num_str, num_str_length, layer + 1, start_index - 3, single_list, ten_to_nineteen_list, Twenty_to_Ninety_list, Three_segmented_list)\n",
    "        translate_3(num_str[start_index - 2:start_index + 1], Twenty_to_Ninety_list, ten_to_nineteen_list, single_list, answer_list)\n",
    "        if int(num_str[start_index - 2:start_index + 1]):\n",
    "            if layer:\n",
    "                answer_list.append(Three_segmented_list[layer])\n",
    "                answer_list.append(' ')\n",
    "            else:\n",
    "                answer_list.pop()\n",
    "        else:\n",
    "            if layer == 0:\n",
    "                answer_list.pop()\n",
    "    else:\n",
    "        if start_index >= 0:\n",
    "            translate_21(num_str[:start_index + 1], Twenty_to_Ninety_list, ten_to_nineteen_list, single_list, answer_list)\n",
    "            if layer:\n",
    "                answer_list.append(Three_segmented_list[layer])\n",
    "                answer_list.append(' ')\n",
    "            else:\n",
    "                answer_list.pop()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        to19='One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen'.split()\n",
    "        tens='Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety'.split()\n",
    "        def helper(num):\n",
    "            if num<20:\n",
    "                return to19[num-1:num]\n",
    "            if num<100:\n",
    "                return [tens[num//10-2]]+helper(num%10)\n",
    "            if num<1000:\n",
    "                return [to19[num//100-1]]+['Hundred']+helper(num%100)\n",
    "            for p,w in enumerate(['Thousand','Million','Billion'],1):\n",
    "                if num<1000**(p+1):\n",
    "                    return helper(num//1000**p)+[w]+helper(num%1000**p)\n",
    "        return ' '.join(helper(num)) or 'Zero'\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return 'Zero'\n",
    "        single_list = ['Zero', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine']\n",
    "        ten_to_nineteen_list = ['Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen']\n",
    "        Twenty_to_Ninety_list = ['Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', \"Ninety\"]\n",
    "        Three_segmented_list = ['Hundred', 'Thousand', 'Million', 'Billion']\n",
    "        num_str = str(num)\n",
    "        num_str_length = len(num_str)\n",
    "        answer_list = list()\n",
    "        dfs(answer_list, num_str, num_str_length, 0, num_str_length - 1, single_list, ten_to_nineteen_list, Twenty_to_Ninety_list, Three_segmented_list)\n",
    "        return ''.join(answer_list)\n",
    "\n",
    "def translate_3(num_str, Twenty_to_Ninety_list, ten_to_nineteen_list, single_list, answer_list):\n",
    "    if num_str[0] != '0':\n",
    "        answer_list.append(single_list[int(num_str[0])])\n",
    "        answer_list.append(' ')\n",
    "        answer_list.append('Hundred')\n",
    "        answer_list.append(' ')\n",
    "    if num_str[1] != '0':\n",
    "        if num_str[1] == '1':\n",
    "            answer_list.append(ten_to_nineteen_list[int(num_str[2])])\n",
    "            answer_list.append(' ')\n",
    "            return\n",
    "        else:\n",
    "            answer_list.append(Twenty_to_Ninety_list[int(num_str[1]) - 2])\n",
    "            answer_list.append(' ')\n",
    "    if num_str[2] != '0':\n",
    "        answer_list.append(single_list[int(num_str[2])])\n",
    "        answer_list.append(' ')\n",
    "\n",
    "def translate_21(num_str, Twenty_to_Ninety_list, ten_to_nineteen_list, single_list, answer_list):\n",
    "    if len(num_str) == 2:\n",
    "        if num_str[0] != '0':\n",
    "            if num_str[0] == '1':\n",
    "                answer_list.append(ten_to_nineteen_list[int(num_str[1])])\n",
    "                answer_list.append(' ')\n",
    "                return \n",
    "            else:\n",
    "                answer_list.append(Twenty_to_Ninety_list[int(num_str[0]) - 2])\n",
    "                answer_list.append(' ')\n",
    "                if num_str[1] != '0':\n",
    "                    answer_list.append(single_list[int(num_str[1])])\n",
    "                    answer_list.append(' ')\n",
    "    else:\n",
    "        if num_str[0] != '0':\n",
    "            answer_list.append(single_list[int(num_str[0])])\n",
    "            answer_list.append(' ')\n",
    "\n",
    "def dfs(answer_list, num_str, num_str_length, layer, start_index, single_list, ten_to_nineteen_list, Twenty_to_Ninety_list, Three_segmented_list):\n",
    "    if num_str_length - 3 >= 0:\n",
    "        num_str_length -= 3 \n",
    "        dfs(answer_list, num_str, num_str_length, layer + 1, start_index - 3, single_list, ten_to_nineteen_list, Twenty_to_Ninety_list, Three_segmented_list)\n",
    "        translate_3(num_str[start_index - 2:start_index + 1], Twenty_to_Ninety_list, ten_to_nineteen_list, single_list, answer_list)\n",
    "        if int(num_str[start_index - 2:start_index + 1]):\n",
    "            if layer:\n",
    "                answer_list.append(Three_segmented_list[layer])\n",
    "                answer_list.append(' ')\n",
    "            else:\n",
    "                answer_list.pop()\n",
    "        else:\n",
    "            if layer == 0:\n",
    "                answer_list.pop()\n",
    "    else:\n",
    "        if start_index >= 0:\n",
    "            translate_21(num_str[:start_index + 1], Twenty_to_Ninety_list, ten_to_nineteen_list, single_list, answer_list)\n",
    "            if layer:\n",
    "                answer_list.append(Three_segmented_list[layer])\n",
    "                answer_list.append(' ')\n",
    "            else:\n",
    "                answer_list.pop()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return 'Zero'\n",
    "        single_list = ['Zero', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine']\n",
    "        ten_to_nineteen_list = ['Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen']\n",
    "        Twenty_to_Ninety_list = ['Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', \"Ninety\"]\n",
    "        Three_segmented_list = ['Hundred', 'Thousand', 'Million', 'Billion']\n",
    "        num_str = str(num)\n",
    "        num_str_length = len(num_str)\n",
    "        answer_list = list()\n",
    "        dfs(answer_list, num_str, num_str_length, 0, num_str_length - 1, single_list, ten_to_nineteen_list, Twenty_to_Ninety_list, Three_segmented_list)\n",
    "        return ''.join(answer_list)\n",
    "\n",
    "def translate_3(num_str, Twenty_to_Ninety_list, ten_to_nineteen_list, single_list, answer_list):\n",
    "    if num_str[0] != '0':\n",
    "        answer_list.append(single_list[int(num_str[0])])\n",
    "        answer_list.append(' ')\n",
    "        answer_list.append('Hundred')\n",
    "        answer_list.append(' ')\n",
    "    if num_str[1] != '0':\n",
    "        if num_str[1] == '1':\n",
    "            answer_list.append(ten_to_nineteen_list[int(num_str[2])])\n",
    "            answer_list.append(' ')\n",
    "            return\n",
    "        else:\n",
    "            answer_list.append(Twenty_to_Ninety_list[int(num_str[1]) - 2])\n",
    "            answer_list.append(' ')\n",
    "    if num_str[2] != '0':\n",
    "        answer_list.append(single_list[int(num_str[2])])\n",
    "        answer_list.append(' ')\n",
    "\n",
    "def translate_21(num_str, Twenty_to_Ninety_list, ten_to_nineteen_list, single_list, answer_list):\n",
    "    if len(num_str) == 2:\n",
    "        if num_str[0] != '0':\n",
    "            if num_str[0] == '1':\n",
    "                answer_list.append(ten_to_nineteen_list[int(num_str[1])])\n",
    "                answer_list.append(' ')\n",
    "                return \n",
    "            else:\n",
    "                answer_list.append(Twenty_to_Ninety_list[int(num_str[0]) - 2])\n",
    "                answer_list.append(' ')\n",
    "                if num_str[1] != '0':\n",
    "                    answer_list.append(single_list[int(num_str[1])])\n",
    "                    answer_list.append(' ')\n",
    "    else:\n",
    "        if num_str[0] != '0':\n",
    "            answer_list.append(single_list[int(num_str[0])])\n",
    "            answer_list.append(' ')\n",
    "\n",
    "def dfs(answer_list, num_str, num_str_length, layer, start_index, single_list, ten_to_nineteen_list, Twenty_to_Ninety_list, Three_segmented_list):\n",
    "    if num_str_length - 3 >= 0:\n",
    "        num_str_length -= 3 \n",
    "        dfs(answer_list, num_str, num_str_length, layer + 1, start_index - 3, single_list, ten_to_nineteen_list, Twenty_to_Ninety_list, Three_segmented_list)\n",
    "        translate_3(num_str[start_index - 2:start_index + 1], Twenty_to_Ninety_list, ten_to_nineteen_list, single_list, answer_list)\n",
    "        if int(num_str[start_index - 2:start_index + 1]):\n",
    "            if layer:\n",
    "                answer_list.append(Three_segmented_list[layer])\n",
    "                answer_list.append(' ')\n",
    "            else:\n",
    "                answer_list.pop()\n",
    "        else:\n",
    "            if layer == 0:\n",
    "                answer_list.pop()\n",
    "    else:\n",
    "        if start_index >= 0:\n",
    "            translate_21(num_str[:start_index + 1], Twenty_to_Ninety_list, ten_to_nineteen_list, single_list, answer_list)\n",
    "            if layer:\n",
    "                answer_list.append(Three_segmented_list[layer])\n",
    "                answer_list.append(' ')\n",
    "            else:\n",
    "                answer_list.pop()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        to19='One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen'.split()\n",
    "        tens='Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety'.split()\n",
    "        def helper(num):\n",
    "            if num<20:\n",
    "                return to19[num-1:num]\n",
    "            if num<100:\n",
    "                return [tens[num//10-2]]+helper(num%10)\n",
    "            if num<1000:\n",
    "                return [to19[num//100-1]]+['Hundred']+helper(num%100)\n",
    "            for p,w in enumerate(['Thousand','Million','Billion'],1):\n",
    "                if num<1000**(p+1):\n",
    "                    return helper(num//1000**p)+[w]+helper(num%1000**p)\n",
    "        return ' '.join(helper(num)) or 'Zero'\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        to19='One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen'.split()\n",
    "        tens='Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety'.split()\n",
    "        def helper(num):\n",
    "            if num<20:\n",
    "                return to19[num-1:num]\n",
    "            if num<100:\n",
    "                return [tens[num//10-2]]+helper(num%10)\n",
    "            if num<1000:\n",
    "                return [to19[num//100-1]]+['Hundred']+helper(num%100)\n",
    "            for p,w in enumerate(['Thousand','Million','Billion'],1):\n",
    "                if num<1000**(p+1):\n",
    "                    return helper(num//1000**p)+[w]+helper(num%1000**p)\n",
    "        return ' '.join(helper(num)) or 'Zero'\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
